package tree;
import java.util.*;
import org.junit.Test;

public class Ex538 {
    class Solution1 {
        //每个搜索二叉树节点的值等于大于等于二叉树节点的和累加
        public TreeNode convertBST(TreeNode root) {
           inOrder(root, 0);
           return root;
        }

        public int inOrder(TreeNode root, int cur) {
            if (root == null) return cur;
            int right = inOrder(root.right, cur);
            root.val = root.val + right; //将右子树的值加到当前根节点上
            int left = inOrder(root.left, root.val); //左子树会加上当前根节点的值
            return left; //返回最左节点的值
        }
    }

    class Solution {
        //每个搜索二叉树节点的值等于大于等于二叉树节点的和累加
        public TreeNode convertBST(TreeNode root) {
            if (root == null) return root;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root; //保留root引用
            int sum = 0;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.right;
                }
                //遍历节点
                cur = stack.pop();
                cur.val += sum;
                sum = cur.val;
                cur = cur.left;
            }
           return root;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        TreeNode root = TreeUtils.createTree(new Integer[]{1,0,2});
        TreeUtils.printBinaryTreeVisualization(root);
        root = s.convertBST(root);
        System.out.println(root.printTree());
        TreeUtils.printBinaryTreeVisualization(root);
    }
}
